#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <unordered_map>
#include <cmath>
#include <ctime>
#include <stack>

using namespace std;
///Users/fyb/Desktop/huawei/dataset/data_fake_big
///Users/fyb/Desktop/huawei/output/solution.txt
string DATADIR = "/Users/fyb/Desktop/huawei/data";
string OUTPUT_FILE = "/Users/fyb/Desktop/huawei/output/solution.txt";

string DEMAND = DATADIR + "/demand.csv";
string SITE_BANDWIDTH = DATADIR + "/site_bandwidth.csv";
string QOS = DATADIR + "/qos.csv";
string CONFIG = DATADIR + "/config.ini";

clock_t startTime, endTime;

class Client_info;

typedef struct current_bd
{
    int clientNum = 0;
    int streamNum = 0;
    int bandwidth = 0;
} BandwidthInfo;
bool cmp1(BandwidthInfo x,BandwidthInfo y){
    return x.bandwidth>y.bandwidth;   //定义降序排序（从大到小）
}
typedef struct redo_log
{
    int k = 0;
    int current_k = 0;
    int bandwidth = 0;
    int streamNum = 0;
    int clientNum = 0;

} Redo_Log;

typedef struct everytime_bdSum
{
    int timeNum = 0;
    int bandwidth = 0;
} EverytimeBdSum;

class Site_Bandwidth_info
{
public:
    vector<string> site_name;             //所有时刻的边缘节点名字
    vector<int> site_bandwidth;           //所有时刻的带宽上限
    unordered_map<string, int> siteToIdx; //用于做site的映射 边缘节点名字->边缘节点在site_bandwidth的下标

    vector<vector<int>> site_to_client; //用来存储每个site连接哪些client :坤坤
    int every_site_max_connect[135];    //用来指示每个site连接的client的数量。:坤坤

    int site_number;
    vector<vector<int>> site_to_site;
    void Set_Site_Name(string name);
    void Set_Site_Bandwidth(int bandwidth);
    void Set_Site_Number(int site_number);
    vector<string> Get_Site_Name()
    {
        return site_name;
    }
    vector<int> Get_Site_Bandwidth()
    {
        return site_bandwidth;
    }
    int Get_site_number()
    {
        return site_number;
    }
    void read_from_scv(std::string filedir); //从scv中读取文件
};
void Site_Bandwidth_info::Set_Site_Name(string name)
{
    site_name.push_back(name);
}
void Site_Bandwidth_info::Set_Site_Bandwidth(int bandwidth)
{
    site_bandwidth.push_back(bandwidth);
}
void Site_Bandwidth_info::Set_Site_Number(int siteNumber)
{
    Site_Bandwidth_info::site_number = siteNumber;
}
void Site_Bandwidth_info::read_from_scv(std::string filedir)
{
    ifstream inFile(filedir, ios::in);
    string line;
    getline(inFile, line);

    stringstream ss(line);
    string str;
    getline(ss, str, ',');
    while (getline(ss, str, ','))
    {
    }
    int tmp_idx = 0;
    while (getline(inFile, line))
    {
        stringstream ss2(line);
        string tmp_str;
        string tmp_str2;
        getline(ss2, tmp_str, ',');
        Set_Site_Name(tmp_str);
        siteToIdx[tmp_str] = tmp_idx++;
        getline(ss2, tmp_str2, ',');
        int a = stoi(tmp_str2);
        Set_Site_Bandwidth(stoi(tmp_str2));
    }

    Set_Site_Number(tmp_idx);
}

class CurrentTime_client_info
{ //每个时刻一个该类，用于记录当前时刻的所有带宽请求。
public:
    vector<std::string> streamName;               ///用来记录每个流的名字
    int current_stream_client_bandwidth[105][40]; ///用来记录当前时刻每一个流的带宽
    /**
     * 用来指示当前时刻每一个流的带宽分配给哪个边缘节点
     */
    int allo_stream_client_toSite[105][40]; ///用来指示当前时刻每一个流的带宽分配给哪个边缘节点  [流id][客户端id]=边缘节点id
    int cost[135];                          ///用来指示当前时刻每一个边缘节点的带宽分配量
    int streamNumber = 0;
    BandwidthInfo bandwidthInfo[3500];
    ///每个时刻一个vector数组，里面存的是一个vector，用于将分配给该节点的流量存入该服务器队列中;
    vector<vector<BandwidthInfo>> site_allo_list; ///服务器的请求队列
    int circle[35];                               ///用来标记当前客户端该优先分给那个服务器
    void init();
    void copy(CurrentTime_client_info currentTimeClientInfo);
};

void CurrentTime_client_info::init()
{
    if (site_allo_list.size() == 0)
        this->site_allo_list.clear();
    else
    {
        for (int i = 0; i < site_allo_list.size(); i++)
        {
            site_allo_list[i].clear();
        }
        site_allo_list.clear();
    }
    this->streamName.clear(); //初始化流名字
    this->streamNumber = 0;
    for (int i = 0; i < 105; i++)
    {
        for (int k = 0; k < 40; k++)
        {
            this->current_stream_client_bandwidth[i][k] = 0;
            this->allo_stream_client_toSite[i][k] = -1;
        }
        cost[i] = 0;
    }
    for (int i = 0; i < 135; i++)
    {
        vector<BandwidthInfo> site_bd;
        this->site_allo_list.push_back(site_bd);
    }
    for (int i = 0; i < 35; i++)
    {
        circle[i] = 0;
    }
}

class Client_info
{
public:
    int client_number;
    int clinet_timestamp_number;
    vector<std::string> client_Name;                       //用来存每个客户端的名字
    vector<CurrentTime_client_info> everyTime_client_info; ///(right)
    unordered_map<string, int> clientToIdx;                // TODO:解决qos乱序 (right)
    /**
     * 用于均分时使用
     * every_client_max_connect[x]=y
     * x：表示客户节点编号
     * y:为最大连接数量
     */

    vector<vector<int>> client_to_site; //用来存每个客户端连接哪些边缘节点
    int every_client_max_connect[35];   //用来指示每个客户端连接的边缘节点的数量。

    Client_info() = default;

    void Set_Client_Number(int client_number);
    void Set_Timestamp_Number(int client_timestamp_number);

    void Set_Client_Name(string name); //添加客户端名字
    void set_client_timestamp_bandwidth_value(int timestamp, int client, int change_bandwidth);

    vector<std::string> Get_Client_Name()
    {
        return client_Name;
    }
    void init();
    void Set_Client_Timestamp_Bandwidth(vector<int> client_bendwith);
    void read_from_scv(std::string filedir); //从scv中读取文件
};
void Client_info::Set_Client_Name(string name)
{
    client_Name.push_back(name);
}
void Client_info::Set_Client_Number(int client_number)
{
    Client_info::client_number = client_number;
}
void Client_info::Set_Timestamp_Number(int timestamp_number)
{
    Client_info::clinet_timestamp_number = timestamp_number;
}
void Client_info::read_from_scv(string filedir)
{
    ifstream inFile(filedir, ios::in);
    string line;
    CurrentTime_client_info currentTimeClientInfo;
    getline(inFile,line,'\r');
    stringstream ss(line);
    string str;

    getline(ss, str, ',');
    getline(ss, str, ',');
    int tmp_idx = 0;
    while (getline(ss, str, ','))
    {

        clientToIdx[str] = tmp_idx++;
        Set_Client_Name(str); //将每个客户端名称放入成员变量中
    }

    Set_Client_Number(tmp_idx);//存入number
    int tmp_stream_number=0;
    int tmp_flag=0;
    string is_equal_str="timestamp";///作为临时变量，用于标记当前时刻与上一时刻是否属于同一时刻
    int index_time=0;
    int current_time=-1;///为什么是-1呢，因为第一个时刻与初试字符串一定不相同，是的第一个时刻以-1+1 、也就是0作为下标开始
    while(getline(inFile, line,'\r')){
        if(line=="\n")break;//读取空行直接跳出

        stringstream ss2(line);
        string tmp_str;
        getline(ss2, tmp_str, ','); /// tmp_str 是读到的时间戳
        /**
         * 判断当前时刻与上一时刻是否属于同一时刻
         * 属于同一时刻，略过
         * 不属于同一时刻，则初始化currentTimeclient。并更新临时时刻变量is_equal_str；并currentTime++;
         */
        if (tmp_str.compare(is_equal_str) == 0)
        {
            ///当前时刻与上一时刻属于同一时刻
        }
        else
        {
            ///当前时刻与上一时刻不属于同一时刻
            is_equal_str = tmp_str;
            if (tmp_flag == 0)
            {
                //这是第一个访问的，所以不用push
                tmp_flag = 1;
            }
            else
            {
                everyTime_client_info.push_back(currentTimeClientInfo); //上一时刻已经结束，push到vector里
            }
            current_time++;
            currentTimeClientInfo.init();
        }

        getline(ss2, tmp_str, ','); /// tmp_str读取到的是流名称
        /**
         * 判断当前流是否处于map中，如果处于，返回下标，如果不处于，赋一个新的下标
         */
        currentTimeClientInfo.streamName.push_back(tmp_str); ///将该流加入vector中

        vector<int> tmp;
        int index_client = 0;
        while (getline(ss2, tmp_str, ','))
        {
            currentTimeClientInfo.current_stream_client_bandwidth[currentTimeClientInfo.streamNumber][index_client] = stoi(tmp_str);
            index_client++;
        }
        currentTimeClientInfo.streamNumber++;
    }
    if (currentTimeClientInfo.streamNumber != 0)
    {
        everyTime_client_info.push_back(currentTimeClientInfo);
        currentTimeClientInfo.init();
    }
    Set_Timestamp_Number(current_time + 1);
}

class QoS_info
{
public:
    int qos_constraint; //用来表示QoS上限
    int base_cost;
    int QoS[200][200]; //用来表示 客户节点与边缘节点的联通关系

    /**
     * 例如client_site_constraint[j][0]=k;
     * j:第J个客户节点；
     * 0：表示第一个连接的边缘节点
     * k:边缘节点编号；
     *
     * 此条语句表示第j个客户节点连接的第一个边缘节点是k；
     * @param filedir
     */
    vector<vector<int>> client_site_constraint; //注意这里是client_site的联通，与QoS二维数组的下标是反的，用来记录client联通的节点是那些

    /**
     * 例如 output[j][k]=5000;
     * j:第j个客户节点
     * k:第k个边缘节点
     * 5000：该客户端分多少给该边缘节点
     *
     */
    vector<vector<vector<int>>> output;

    void read_QoS_from_scv(std::string filedir, unordered_map<string, int> &clientToIdx, unordered_map<string, int> &siteToIdx); //从scv中读取文件
    void read_QoS_constraint_from_scv(std::string filedir);                                                                      //从scv中读取文件
    void read_client_to_site(Client_info &clientInfo, Site_Bandwidth_info &siteBandwidthInfo);
    void set_Qos(int is_connect);
    void set_QoS_constraint(int constraint);
    int get_QoS(int x, int y)
    {
        return QoS[x][y];
    }
};
void QoS_info::read_client_to_site(Client_info &clientInfo, Site_Bandwidth_info &siteBandwidthInfo)
{
    clientInfo.client_to_site.clear();
    int tmp_client = clientInfo.client_number;
    int tmp_site = siteBandwidthInfo.site_number;

    // 坤坤[开始]：添加site连接的client_id及其数量
    for (int j = 0; j < tmp_client; j++)
    {
        vector<int> client_to_site_tmp;
        clientInfo.client_to_site.push_back(client_to_site_tmp);
        clientInfo.every_client_max_connect[j] = 0;
    }

    for (int k = 0; k < tmp_site; k++)
    {
        vector<int> site_to_client_tmp;
        siteBandwidthInfo.site_to_client.push_back(site_to_client_tmp);
        siteBandwidthInfo.every_site_max_connect[k] = 0;
    }

    for (int j = 0; j < tmp_client; j++)
    {
        for (int k = 0; k < tmp_site; k++)
        {
            if (QoS[k][j] == 1)
            { // k边缘节点与j客户节点连通
                clientInfo.client_to_site[j].push_back(k);
                clientInfo.every_client_max_connect[j] += 1;

                siteBandwidthInfo.site_to_client[k].push_back(j);
                siteBandwidthInfo.every_site_max_connect[k] += 1;
            }
        }
    }
    // 坤坤[结束]：添加site连接的client_id及其数量
}
void QoS_info::read_QoS_from_scv(std::string filedir, unordered_map<string, int> &clientToIdx, unordered_map<string, int> &siteToIdx)
{
    ifstream inFile(filedir, ios::in);
    string line;
    getline(inFile,line,'\r');
    stringstream ss(line);
    string str;
    getline(ss, str, ',');
    vector<int> idxOfClient;
    while (getline(ss, str, ','))
    {
        idxOfClient.push_back(clientToIdx[str]);
    }
    int x = 0, y = 0;
    // getline(inFile, line); //跳过\n 坤坤：受win换行符影响，注释掉了这一行
    while (getline(inFile, line))
    {
        stringstream ss2(line);
        string tmp_str;
        getline(ss2, tmp_str, ',');
        x = siteToIdx[tmp_str]; //处理qos乱序
        while (getline(ss2, tmp_str, ','))
        {
            if (stoi(tmp_str) < qos_constraint)
            {
                QoS[x][idxOfClient[y]] = 1;
            }
            else
                QoS[x][idxOfClient[y]] = 0;
            y++;
        }
        y = 0;
    }
}
void QoS_info::set_QoS_constraint(int constraint)
{
    QoS_info::qos_constraint = constraint;
}
void QoS_info::read_QoS_constraint_from_scv(std::string filedir)
{
    ifstream inFile(filedir, ios::in);
    string line;
    getline(inFile, line);
    stringstream ss(line);
    string str;
    getline(ss, str, ',');

    // TODO:  避免constrain与base乱序
    int flag = 0;
    while (getline(inFile, line))
    {
        stringstream ss2(line);
        string tmp_str;
        getline(ss2, tmp_str, '=');

        getline(ss2, tmp_str, '=');
        if (flag == 0)
        {
            set_QoS_constraint(stoi(tmp_str));
            flag++;
        }
        else
        {
            base_cost = stoi(tmp_str);
        }
    }
}

/**
 * 用于检测错误的方法
 * @param clientInfo
 * @param siteBandwidthInfo
 * @param qoSInfo
 */
void check_error(Client_info &clientInfo, Site_Bandwidth_info &siteBandwidthInfo, QoS_info &qoSInfo)
{
    for (int i = 0; i < clientInfo.everyTime_client_info.size(); i++)
    {
        long long sum_client = 0;
        long long sum_site = 0;
        for (int k = 0; k < siteBandwidthInfo.site_number; k++)
        {
            if (clientInfo.everyTime_client_info[i].cost[k] > siteBandwidthInfo.site_bandwidth[k])
            {
                cout << clientInfo.everyTime_client_info[i].cost[k] << endl;
                cout << siteBandwidthInfo.site_bandwidth[k] << endl;
                cout << "边缘节点的上限超了！" << endl;
                throw new exception;
            }
            sum_site += clientInfo.everyTime_client_info[i].cost[k];
        }

        for (int s = 0; s < clientInfo.everyTime_client_info[i].streamNumber; s++)
        {
            for (int j = 0; j < clientInfo.client_number; j++)
            {
                if (clientInfo.everyTime_client_info[i].allo_stream_client_toSite[s][j] == -1)
                {
                    cout << "时刻：" << i << "流：" << s << "客户节点：" << j << "没有分配出去" << endl;
                    throw new exception;
                }
                sum_client += clientInfo.everyTime_client_info[i].current_stream_client_bandwidth[s][j];
            }
        }
        if (sum_client != sum_site)
        {
            cout << "客户总的分配和边缘总分配不等！" << endl;
            throw new exception;
        }
    }
}

double sum_cost(Client_info &clientInfo, Site_Bandwidth_info siteBandwidthInfo, QoS_info qoSInfo)
{
    float up_limit = 0.95;
    float down_limit = 0.94;
    int up_bandwidth[200];   //记录每个边缘节点的0.95分位点处带宽
    int down_bandwidth[200]; //记录每个边缘节点的dowm_limit分位点处带宽
    double sum = 0;
    for (int j = 0; j < siteBandwidthInfo.site_number; j++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[j];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);
        int tmp_up = ceil(clientInfo.clinet_timestamp_number * up_limit)-1;
        up_bandwidth[j] = sort_list[tmp_up];
        int tmp_down = ceil(clientInfo.clinet_timestamp_number * down_limit);
        down_bandwidth[j] = sort_list[tmp_down];
    }
    for (int k = 0; k < siteBandwidthInfo.site_number; k++)
    {
        double tmp = double((up_bandwidth[k] * up_bandwidth[k]) / siteBandwidthInfo.site_bandwidth[k]) + up_bandwidth[k];
        sum += tmp;
    }
    cout << "总带宽成本为：" << sum << endl;
    return sum;
}

void kunkun_local_optimization(Client_info &clientInfo, Site_Bandwidth_info siteBandwidthInfo, QoS_info qoSInfo, float up, float down)
{
    float up_limit = up;
    float down_limit = down;
    int up_bandwidth[200];   //记录每个边缘节点的0.95分位点处带宽
    int down_bandwidth[200]; //记录每个边缘节点的dowm_limit分位点处带宽
    /**
     * 更新0.95 和0.94分位点的带宽
     */
    for (int j = 0; j < siteBandwidthInfo.site_number; j++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[j];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);
        int tmp_up = ceil(clientInfo.clinet_timestamp_number * up_limit)-1;
        up_bandwidth[j] = sort_list[tmp_up];
        int tmp_down = ceil(clientInfo.clinet_timestamp_number * down_limit);
        down_bandwidth[j] = sort_list[tmp_down];
    }

    /**
     * 开始遍历每个时刻，拿到每个时刻的要被分配的带宽
     */

    for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
    {

        for (int k = 0; k < siteBandwidthInfo.site_number; k++)
        {
            if (clientInfo.everyTime_client_info[i].cost[k] <= up_bandwidth[k] && clientInfo.everyTime_client_info[i].cost[k] >= down_bandwidth[k])
            {
                /**
                 * 当前节点是小于等于0.95,并且大于等于0.94的点，需要被分配出去
                 */
                //                cout<<up_bandwidth[k] <<" "<<down_bandwidth[k]<<endl;
                //                cout << "当前时刻：" << i << "--第" << k << "个边缘节点需要被分配，分配带宽为：" << clientInfo.everyTime_client_info[i].cost[k] << endl;
                /**
                 * 依次处理挂载在该节点上的每个流量
                 */

                int is_allo = 0;
                for (int hand_back_index = 0; hand_back_index < clientInfo.everyTime_client_info[i].site_allo_list[k].size(); hand_back_index++)
                {
                    BandwidthInfo current_bandwidthIfo = clientInfo.everyTime_client_info[i].site_allo_list[k][hand_back_index];
                    /**
                     * 找到当前这个结构体能否分出去，如果能，就直接分，跳出循环，如果不能就往下走
                     */
                    //                    cout<<"第"<<k<<"个边缘节点的第"<<hand_back_index<<"个流为"<<current_bandwidthIfo.bandwidth<<endl;
                    ///遍历这个流量属于的那个客户端连接的所有边缘节点，是否有可以放入0.95以后，或者0.94以前。
                    int current_j = current_bandwidthIfo.clientNum;
                    /**
                     * 遍历这个客户节点连接的所有服务节点，是否有满足条件吧这个分过去的
                     */
                    for (int ii = 0; ii < clientInfo.every_client_max_connect[current_j]; ii++)
                    {
                        int tmp_k_index = (clientInfo.everyTime_client_info[i].circle[current_j] + ii) % clientInfo.every_client_max_connect[current_j];
                        int current_k = clientInfo.client_to_site[current_j][tmp_k_index];
                        if (current_k == k)
                            continue;
                        /**
                         * 找到一个满足条件的。当前该客户节点是大于0.95分位点的点。给他分配！
                         */
                        if (clientInfo.everyTime_client_info[i].cost[current_k] > up_bandwidth[current_k])
                        {
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= siteBandwidthInfo.site_bandwidth[current_k])
                            {
                                //访问的这个服务器节点满足要求，可以分配

                                clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                hand_back_index--; //因为erase完以后，总的size会减1，所以需要--

                                //                                cout<<"这个流属于客户节点"<<current_bandwidthIfo.clientNum<<"可以分配给边缘节点------"<<current_k<<endl;
                                //                                cout<<"要分配的这个结点的带宽为："<<clientInfo.everyTime_client_info[i].cost[current_k]<<endl;
                                clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];


                                break;
                            }
                        }
                            /**
                             * 当前客户节点是小于等于0.94分位点的点，给他分配！
                             */
                        else if (clientInfo.everyTime_client_info[i].cost[current_k] <= down_bandwidth[current_k])
                        {
                            //                            int V=qoSInfo.base_cost;
                            //                            int C_k=siteBandwidthInfo.site_bandwidth[k];
                            //                            int C_current=siteBandwidthInfo.site_bandwidth[current_k];
                            //                            int S=clientInfo.everyTime_client_info[i].cost[k]+clientInfo.everyTime_client_info[i].cost[current_k];
                            //                            double S_k=double ((C_current*V-C_k*V+S*C_k)/(C_k+C_current));
                            //                            double S_current=double((C_k*V-C_current*V+S*C_current)/(C_k+C_current));
                            //
                            //                            int allo_S_k=clientInfo.everyTime_client_info[i].cost[k]-current_bandwidthIfo.bandwidth;
                            //                            int allo_S_current=clientInfo.everyTime_client_info[i].cost[current_k]+current_bandwidthIfo.bandwidth;
                            //                            if(allo_S_k>S_k&&allo_S_k>=allo_S_current){//分配完以后的两个均值尽量相等
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= down_bandwidth[current_k])
                            {
                                clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                hand_back_index--;

                                //                                cout<<"这个流属于客户节点"<<current_bandwidthIfo.clientNum<<"可以分配给边缘节点------"<<current_k<<endl;
                                //                                cout<<"要分配的这个结点的带宽为："<<clientInfo.everyTime_client_info[i].cost[current_k]<<endl;
                                clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];

                                /**
                                 * 加入回放栈，
                                 */

                                break;
                                //                                }
                            }
                        }
                    }
                    if (clientInfo.everyTime_client_info[i].cost[k] <= down_bandwidth[k])
                    {
                        ///此时这个结点已经分到0.94以下，跳出
                        is_allo = 1;
                        break;
                    }
                    if (hand_back_index == clientInfo.everyTime_client_info[i].site_allo_list[k].size() - 1)
                    {
                        /**
                         * 此时已经达到局部最小解了，需要调整后0.05分位点的值
                         */
                        //                         cout<<"你进来了"<<endl;
                        //                         for(int gb_i=0;gb_i<clientInfo.clinet_timestamp_number;gb_i++){
                        //
                        //                             if(clientInfo.everyTime_client_info[gb_i].cost[k]>up_bandwidth[k]){
                        //
                        //                                 /**
                        //                                  * 对当前时刻进行预分配，看看预分配的结果能否实现调整。
                        //                                  * 尝试能否将这个极端分配节点移到0.95前面去；
                        //                                  */
                        //
                        //                                 CurrentTime_client_info tmp_currentTime_client_info;
                        //                                 tmp_currentTime_client_info.init();
                        //                                 tmp_currentTime_client_info.copy(clientInfo.everyTime_client_info[gb_i]);
                        ////                                 CurrentTime_client_info tmp_currentTime_client_info=clientInfo.everyTime_client_info[gb_i];
                        //
                        //
                        //                                 int is_allo=0;//用于标识该节点在预分配过程中是否可以完成分配。
                        //                                 for(int gb_hand_back_index=0;gb_hand_back_index<tmp_currentTime_client_info.site_allo_list[k].size();gb_hand_back_index++){
                        //                                    BandwidthInfo tmp_current_bandwidthInfo=tmp_currentTime_client_info.site_allo_list[k][gb_hand_back_index];
                        //                                    ///尝试把结构体分出去。
                        //                                     int tmp_current_j=tmp_current_bandwidthInfo.clientNum;
                        //                                    for(int tmp_ii=0;tmp_ii<clientInfo.every_client_max_connect[tmp_current_j];tmp_ii++){
                        //
                        //                                        int tmp_tmp_k_index=(tmp_currentTime_client_info.circle[tmp_current_j]+tmp_ii)%clientInfo.every_client_max_connect[tmp_current_j];
                        //                                        int tmp_current_k=clientInfo.client_to_site[tmp_current_j][tmp_tmp_k_index];
                        //                                        if(k==tmp_current_k)continue;
                        //                                        if(tmp_currentTime_client_info.cost[tmp_current_k]>up_bandwidth[tmp_current_k]) {
                        //                                            ///这是一个大于0.95分位点的点，尝试分配给它
                        //                                            if(tmp_currentTime_client_info.cost[tmp_current_k]+tmp_current_bandwidthInfo.bandwidth<=siteBandwidthInfo.site_bandwidth[tmp_current_k]) {
                        //                                                tmp_currentTime_client_info.cost[tmp_current_k]+=tmp_current_bandwidthInfo.bandwidth;
                        //                                                tmp_currentTime_client_info.cost[k]-=tmp_current_bandwidthInfo.bandwidth;
                        //                                                tmp_currentTime_client_info.allo_stream_client_toSite[tmp_current_bandwidthInfo.streamNum][tmp_current_bandwidthInfo.clientNum]=tmp_current_k;
                        //                                                tmp_currentTime_client_info.site_allo_list[k].erase(std::begin(tmp_currentTime_client_info.site_allo_list[k])+gb_hand_back_index);
                        //                                                tmp_currentTime_client_info.site_allo_list[tmp_current_k].push_back(tmp_current_bandwidthInfo);
                        //                                                gb_hand_back_index--;//因为erase完以后，总的size会减1，所以需要--
                        //                                                tmp_currentTime_client_info.circle[tmp_current_j]=(tmp_tmp_k_index+1)%clientInfo.every_client_max_connect[tmp_current_j];
                        //                                                break;
                        //                                            }
                        //                                        }
                        //                                        else if(tmp_currentTime_client_info.cost[tmp_current_k]<down_bandwidth[tmp_current_k]){
                        //                                            ///这是一个小于0.94分位点的点，尝试分配给它
                        //                                            if(tmp_currentTime_client_info.cost[tmp_current_k]+tmp_current_bandwidthInfo.bandwidth<=down_bandwidth[tmp_current_k]){
                        //                                                tmp_currentTime_client_info.cost[tmp_current_k]+=tmp_current_bandwidthInfo.bandwidth;
                        //                                                tmp_currentTime_client_info.cost[k]-=tmp_current_bandwidthInfo.bandwidth;
                        //                                                tmp_currentTime_client_info.allo_stream_client_toSite[tmp_current_bandwidthInfo.streamNum][tmp_current_bandwidthInfo.clientNum]=tmp_current_k;
                        //                                                tmp_currentTime_client_info.site_allo_list[k].erase(std::begin(tmp_currentTime_client_info.site_allo_list[k])+gb_hand_back_index);
                        //                                                tmp_currentTime_client_info.site_allo_list[tmp_current_k].push_back(tmp_current_bandwidthInfo);
                        //                                                gb_hand_back_index--;
                        //                                                tmp_currentTime_client_info.circle[tmp_current_j]=(tmp_tmp_k_index+1)%clientInfo.every_client_max_connect[tmp_current_j];
                        //                                                break;
                        //                                             }
                        //                                        }
                        ////
                        //                                    }
                        //                                    if(tmp_currentTime_client_info.cost[k]<=down_bandwidth[k]){
                        //                                         ///此时这个结点已经分到0.94以下，跳出
                        //                                         is_allo=1;//表示这个结点可以放到前面去！
                        //                                         break;
                        //                                    }
                        //                                    if(gb_hand_back_index==tmp_currentTime_client_info.site_allo_list[k].size()-1){
                        //                                         is_allo=0;
                        //                                    }
                        //
                        //
                        //                                 }
                        //                                 if(is_allo==1){
                        //                                     /**
                        //                                      * 该节点可以分配，那就这么做吧
                        //                                      */
                        //                                     clientInfo.everyTime_client_info[gb_i].copy(tmp_currentTime_client_info);
                        ////                                     for(int gb_hand_back_index=0;gb_hand_back_index<clientInfo.everyTime_client_info[gb_i].site_allo_list[k].size();gb_hand_back_index++){
                        ////                                         BandwidthInfo tmp_current_bandwidthInfo=clientInfo.everyTime_client_info[gb_i].site_allo_list[k][gb_hand_back_index];
                        ////                                         ///尝试把结构体分出去。
                        ////                                         int tmp_current_j=tmp_current_bandwidthInfo.clientNum;
                        ////                                         for(int tmp_ii=0;tmp_ii<clientInfo.every_client_max_connect[tmp_current_j];tmp_ii++){
                        ////
                        ////                                             int tmp_tmp_k_index=(clientInfo.everyTime_client_info[gb_i].circle[tmp_current_j]+tmp_ii)%clientInfo.every_client_max_connect[tmp_current_j];
                        ////                                             int tmp_current_k=clientInfo.client_to_site[tmp_current_j][tmp_tmp_k_index];
                        ////                                             if(clientInfo.everyTime_client_info[gb_i].cost[tmp_current_k]>up_bandwidth[tmp_current_k]) {
                        ////                                                 ///这是一个大于0.95分位点的点，尝试分配给它
                        ////                                                 if(clientInfo.everyTime_client_info[gb_i].cost[tmp_current_k]+tmp_current_bandwidthInfo.bandwidth<=siteBandwidthInfo.site_bandwidth[tmp_current_k]) {
                        ////                                                     clientInfo.everyTime_client_info[gb_i].cost[tmp_current_k]+=tmp_current_bandwidthInfo.bandwidth;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].cost[k]-=tmp_current_bandwidthInfo.bandwidth;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].allo_stream_client_toSite[tmp_current_bandwidthInfo.streamNum][tmp_current_bandwidthInfo.clientNum]=tmp_current_k;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[gb_i].site_allo_list[k])+gb_hand_back_index);
                        ////                                                     clientInfo.everyTime_client_info[gb_i].site_allo_list[tmp_current_k].push_back(tmp_current_bandwidthInfo);
                        ////                                                     gb_hand_back_index--;//因为erase完以后，总的size会减1，所以需要--
                        ////                                                     clientInfo.everyTime_client_info[gb_i].circle[tmp_current_j]=(tmp_tmp_k_index+1)%clientInfo.every_client_max_connect[tmp_current_j];
                        ////                                                     break;
                        ////                                                 }
                        ////                                             }else if(clientInfo.everyTime_client_info[gb_i].cost[tmp_current_k]<down_bandwidth[tmp_current_k]){
                        ////                                                 ///这是一个小于0.94分位点的点，尝试分配给它
                        ////                                                 if(clientInfo.everyTime_client_info[gb_i].cost[tmp_current_k]+tmp_current_bandwidthInfo.bandwidth<=down_bandwidth[tmp_current_k]){
                        ////                                                     clientInfo.everyTime_client_info[gb_i].cost[tmp_current_k]+=tmp_current_bandwidthInfo.bandwidth;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].cost[k]-=tmp_current_bandwidthInfo.bandwidth;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].allo_stream_client_toSite[tmp_current_bandwidthInfo.streamNum][tmp_current_bandwidthInfo.clientNum]=tmp_current_k;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[gb_i].site_allo_list[k])+gb_hand_back_index);
                        ////                                                     clientInfo.everyTime_client_info[gb_i].site_allo_list[tmp_current_k].push_back(tmp_current_bandwidthInfo);
                        ////                                                     gb_hand_back_index--;
                        ////                                                     clientInfo.everyTime_client_info[gb_i].circle[tmp_current_j]=(tmp_tmp_k_index+1)%clientInfo.every_client_max_connect[tmp_current_j];
                        ////                                                     break;
                        ////                                                 }
                        ////                                             }
                        //////
                        ////                                         }
                        ////                                         if(clientInfo.everyTime_client_info[gb_i].cost[k]<=down_bandwidth[k]){
                        ////                                             ///此时这个结点已经分到0.94以下，跳出
                        //////                                             is_allo=1;//表示这个结点可以放到前面去！
                        ////                                             break;
                        ////                                         }
                        ////
                        ////
                        ////
                        ////                                     }
                        //
                        //                                     /**
                        //                                      * 该节点已经分配到0.94的范围了，这时候需要重新调整一下第k个边缘节点的0.95分位点
                        //                                      */
                        ////                                     for(int t_k=0;t_k<siteBandwidthInfo.site_number;t_k++){
                        //                                         int t_sort_list[clientInfo.clinet_timestamp_number];
                        //                                         for(int t_i=0;t_i<clientInfo.clinet_timestamp_number;t_i++){
                        //                                             t_sort_list[t_i]=clientInfo.everyTime_client_info[t_i].cost[k];
                        //                                         }
                        //                                         sort(t_sort_list,t_sort_list+clientInfo.clinet_timestamp_number);
                        //                                         int ttmp_up=ceil(clientInfo.clinet_timestamp_number*up_limit);
                        //                                         up_bandwidth[k]=t_sort_list[ttmp_up];
                        //                                         int ttmp_down=ceil(clientInfo.clinet_timestamp_number*down_limit);
                        //                                         down_bandwidth[k]=t_sort_list[ttmp_down];
                        ////                                     }
                        //
                        //
                        //
                        //                                 }
                        //
                        //
                        //                             }
                        //
                        //                         }
                    }
                }
                if (is_allo == 1)
                {
                    /**
                     * 该节点可以分配，那就这么做吧
                     */
                    //                    clientInfo.everyTime_client_info[i].copy(tmp_currentTime_client_info);
                    //                    cout<<"可以执行，清空栈"<<endl;

                    /**
                     * 该节点已经分配到0.94的范围了，这时候需要重新调整一下第k个边缘节点的0.95分位点
                     */
                }
                else if (is_allo == 0)
                {
                    /**
                     * 不可以这么做，执行日志回访操作
                     */
                    //                     cout<<"不可以执行，进行回放"<<endl;


                }
            }
        }
    }
}
void sort_everytime(Client_info &clientInfo,Site_Bandwidth_info siteBandwidthInfo,QoS_info qoSInfo) {
    int bdNum=clientInfo.everyTime_client_info[0].streamNumber*clientInfo.client_number;
    int j_limit=clientInfo.client_number;
    //clientInfo.everyTime_client_info.size()
    for(int i=0;i<clientInfo.everyTime_client_info.size();i++){///依次分配每一个时刻
//        BandwidthInfo bandwidthInfo[bdNum];
        int db_index=0;
        int s_limit=clientInfo.everyTime_client_info[i].streamNumber;
        /**
         * 将当前时刻读入结构体
         */
        for(int s=0;s<s_limit;s++){
            for(int j=0;j<j_limit;j++){
                clientInfo.everyTime_client_info[i].bandwidthInfo[db_index].clientNum=j;
                clientInfo.everyTime_client_info[i].bandwidthInfo[db_index].streamNum=s;
                clientInfo.everyTime_client_info[i].bandwidthInfo[db_index].bandwidth=clientInfo.everyTime_client_info[i].current_stream_client_bandwidth[s][j];
//                cout<<bandwidthInfo[db_index].bandwidth<<endl;

                db_index++;
            }
        }
        /**
         * 对当前时刻进行排序
         */
        sort( clientInfo.everyTime_client_info[i].bandwidthInfo, clientInfo.everyTime_client_info[i].bandwidthInfo+bdNum,cmp1);

        /**
         * 对当前时刻进行分配
         * site_current_index:用于指示当前访问到哪个边缘节点
         * bandwidthInfo :当前时刻要处理的结构体
         * clientInfo.every_client_max_connect:每个客户节点连接的边缘节点的数量
         * clientInfo.client_to_site[j][i]=y 每个客户节点连接的具体边缘节点。j表示客户节点编号，i表示第i个相连的边缘节点,y表示边缘节点的编号
         */
//        int site_current_index=0;
//        int db_current=0;
//        int select_site[clientInfo.client_number];
//        for(int tmp=0;tmp<clientInfo.client_number;tmp++)select_site[tmp]=0;
//
//        int circle_index[clientInfo.client_number];  //用于均分时，每个遍历一次
//        for(int tt=0;tt<clientInfo.client_number;tt++){
//            circle_index[tt]=0;
//        }
//
//        //bdNum
//        while(db_current<bdNum){
//            /*
//             * 遍历与当前客户节点相连的所有边。
//             */
//
//            int current_j= clientInfo.everyTime_client_info[i].bandwidthInfo[db_current].clientNum;
//            int current_bandwidth= clientInfo.everyTime_client_info[i].bandwidthInfo[db_current].bandwidth;
//            int current_s= clientInfo.everyTime_client_info[i].bandwidthInfo[db_current].streamNum;
////            cout<<current_s<<" "<<current_j<<" "<<current_bandwidth<<endl;
//            for(int ii=0;ii<clientInfo.every_client_max_connect[current_j];ii++){
//                int current_ii=(circle_index[current_j]+ii)%clientInfo.every_client_max_connect[current_j];
//
//
//                int current_k=clientInfo.client_to_site[current_j][current_ii];//当前要给带宽的边缘节点编号
////                cout<<current_bandwidth<<endl;
//                if(clientInfo.everyTime_client_info[i].cost[current_k]+current_bandwidth<=siteBandwidthInfo.site_bandwidth[current_k]){
//                    ///当前边缘节点可以分配，那就分配
//                    circle_index[current_j]=(current_ii+1)%clientInfo.every_client_max_connect[current_j];
//                    /**
//                     * 执行分配
//                     * cost增加
//                     * clientInfo.everyTime_client_info[i].allo_stream_client_toSite指向分配的边缘节点
//                     *
//                     *
//                     */
//                     clientInfo.everyTime_client_info[i].cost[current_k]+=current_bandwidth;
//                     clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_s][current_j]=current_k;
//                    break;
//                }
//
//            }
//
//            db_current++;
//        }
    }

//    check_error(clientInfo,siteBandwidthInfo,qoSInfo);
}
void average_everytime(Client_info &clientInfo,Site_Bandwidth_info siteBandwidthInfo,QoS_info qoSInfo) {
    int bdNum=clientInfo.everyTime_client_info[0].streamNumber*clientInfo.client_number;
    int j_limit=clientInfo.client_number;
    //clientInfo.everyTime_client_info.size()

    for(int i=0;i<clientInfo.everyTime_client_info.size();i++){///依次分配每一个时刻
        int bdNum=clientInfo.everyTime_client_info[0].streamNumber*clientInfo.client_number;
//        BandwidthInfo bandwidthInfo[bdNum];
        int db_index=0;
        int s_limit=clientInfo.everyTime_client_info[i].streamNumber;
        /**
         * 对当前时刻进行分配
         * site_current_index:用于指示当前访问到哪个边缘节点
         * bandwidthInfo :当前时刻要处理的结构体
         * clientInfo.every_client_max_connect:每个客户节点连接的边缘节点的数量
         * clientInfo.client_to_site[j][i]=y 每个客户节点连接的具体边缘节点。j表示客户节点编号，i表示第i个相连的边缘节点,y表示边缘节点的编号
         */
        int site_current_index=0;
        int db_current=0;
        int select_site[clientInfo.client_number];
        for(int tmp=0;tmp<clientInfo.client_number;tmp++)select_site[tmp]=0;

        int circle_index[clientInfo.client_number];  //用于均分时，每个遍历一次
        for(int tt=0;tt<clientInfo.client_number;tt++){
            circle_index[tt]=0;
        }

        //bdNum
        while(db_current<bdNum){
            /*
             * 遍历与当前客户节点相连的所有边。
             */

            int current_j= clientInfo.everyTime_client_info[i].bandwidthInfo[db_current].clientNum;
            int current_bandwidth= clientInfo.everyTime_client_info[i].bandwidthInfo[db_current].bandwidth;
            int current_s= clientInfo.everyTime_client_info[i].bandwidthInfo[db_current].streamNum;
//            cout<<current_s<<" "<<current_j<<" "<<current_bandwidth<<endl;
            for(int ii=0;ii<clientInfo.every_client_max_connect[current_j];ii++){
                int current_ii=(circle_index[current_j]+ii)%clientInfo.every_client_max_connect[current_j];


                int current_k=clientInfo.client_to_site[current_j][current_ii];//当前要给带宽的边缘节点编号
//                cout<<current_bandwidth<<endl;
                if(clientInfo.everyTime_client_info[i].cost[current_k]+current_bandwidth<=siteBandwidthInfo.site_bandwidth[current_k]){
                    ///当前边缘节点可以分配，那就分配
                    circle_index[current_j]=(current_ii+1)%clientInfo.every_client_max_connect[current_j];

                    /**
                     * 执行分配
                     * 服务器节点push一个结构体元素
                     * cost增加
                     * clientInfo.everyTime_client_info[i].allo_stream_client_toSite指向分配的边缘节点
                     *
                     *
                     */
                    BandwidthInfo tmp_db=clientInfo.everyTime_client_info[i].bandwidthInfo[db_current];
                    clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(tmp_db);
//                    cout<<tmp_db.streamNum<<" "<<tmp_db.clientNum<<" "<<tmp_db.bandwidth<<endl;

//                    cout<<current_s<<" "<<current_j<<" "<<current_bandwidth<<endl;
                    clientInfo.everyTime_client_info[i].cost[current_k]+=current_bandwidth;
                    clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_s][current_j]=current_k;
                    break;
                }


            }

            db_current++;
        }

    }

//    check_error(clientInfo,siteBandwidthInfo,qoSInfo);
}
void kunkun_dream2_local_optimization(Client_info &clientInfo, Site_Bandwidth_info siteBandwidthInfo, QoS_info qoSInfo, float up, float down, double *dream_cost)
{
    float up_limit = up;
    float down_limit = down;
    int up_bandwidth[200];   //记录每个边缘节点的0.95分位点处带宽
    int down_bandwidth[200]; //记录每个边缘节点的dowm_limit分位点处带宽
    /**
     * 更新0.95 和0.94分位点的带宽
     */
    for (int j = 0; j < siteBandwidthInfo.site_number; j++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[j];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);
        int tmp_up = ceil(clientInfo.clinet_timestamp_number * up_limit);
        up_bandwidth[j] = sort_list[tmp_up];
        int tmp_down = ceil(clientInfo.clinet_timestamp_number * down_limit);
        down_bandwidth[j] = sort_list[tmp_down];
    }

    /**
     * 开始遍历每个时刻，拿到每个时刻的要被分配的带宽
     */
    for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
    {

        for (int k = 0; k < siteBandwidthInfo.site_number; k++)
        {
            // clientInfo.everyTime_client_info[i].cost[k]<=up_bandwidth[k]&&clientInfo.everyTime_client_info[i].cost[k]>dream_cost[k]
            if (clientInfo.everyTime_client_info[i].cost[k] > dream_cost[k])
            {
                /**
                 * 当前节点是小于等于0.95,并且大于等于0.94的点，需要被分配出去
                 */
                //                cout<<up_bandwidth[k] <<" "<<down_bandwidth[k]<<endl;
                //                cout << "当前时刻：" << i << "--第" << k << "个边缘节点需要被分配，分配带宽为：" << clientInfo.everyTime_client_info[i].cost[k] << endl;
                /**
                 * 依次处理挂载在该节点上的每个流量
                 */
                if (up_bandwidth[k] < dream_cost[k])
                    continue;
                for (int hand_back_index = 0; hand_back_index < clientInfo.everyTime_client_info[i].site_allo_list[k].size(); hand_back_index++)
                {
                    BandwidthInfo current_bandwidthIfo = clientInfo.everyTime_client_info[i].site_allo_list[k][hand_back_index];
                    /**
                     * 找到当前这个结构体能否分出去，如果能，就直接分，跳出循环，如果不能就往下走
                     */
                    //                    cout<<"第"<<k<<"个边缘节点的第"<<hand_back_index<<"个流为"<<current_bandwidthIfo.bandwidth<<endl;
                    ///遍历这个流量属于的那个客户端连接的所有边缘节点，是否有可以放入0.95以后，或者0.94以前。
                    int current_j = current_bandwidthIfo.clientNum;
                    /**
                     * 遍历这个客户节点连接的所有服务节点，是否有满足条件吧这个分过去的
                     */
                    for (int ii = 0; ii < clientInfo.every_client_max_connect[current_j]; ii++)
                    {
                        int tmp_k_index = (clientInfo.everyTime_client_info[i].circle[current_j] + ii) % clientInfo.every_client_max_connect[current_j];
                        int current_k = clientInfo.client_to_site[current_j][tmp_k_index];
                        if (current_k == k)
                            continue;
                        /**
                         * 找到一个满足条件的。当前该客户节点是大于0.95分位点的点。给他分配！
                         */

                        /**
                         * 当前客户节点是小于等于0.94分位点的点，给他分配！
                         */

                        if (clientInfo.everyTime_client_info[i].cost[current_k] < dream_cost[current_k])
                        {
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= dream_cost[current_k] &&
                                clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= siteBandwidthInfo.site_bandwidth[current_k])
                            {

                                clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                hand_back_index--;

                                //                                cout<<"这个流属于客户节点"<<current_bandwidthIfo.clientNum<<"可以分配给边缘节点------"<<current_k<<endl;
                                //                                cout<<"要分配的这个结点的带宽为："<<clientInfo.everyTime_client_info[i].cost[current_k]<<endl;
                                clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];
                                break;
                            }
                        }
                        else if (clientInfo.everyTime_client_info[i].cost[current_k] > up_bandwidth[current_k])
                        {
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= siteBandwidthInfo.site_bandwidth[current_k])
                            {
                                //访问的这个服务器节点满足要求，可以分配
                                if (up_bandwidth[k] > dream_cost[k])
                                {
                                    clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                    clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                    clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                    clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                    clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                    hand_back_index--; //因为erase完以后，总的size会减1，所以需要--

                                    //                                cout<<"这个流属于客户节点"<<current_bandwidthIfo.clientNum<<"可以分配给边缘节点------"<<current_k<<endl;
                                    //                                cout<<"要分配的这个结点的带宽为："<<clientInfo.everyTime_client_info[i].cost[current_k]<<endl;
                                    clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];
                                    break;
                                }
                            }
                        }
                    }
                    if (clientInfo.everyTime_client_info[i].cost[k] <= dream_cost[k])
                    {
                        ///此时这个结点已经分到0.94以下，跳出
                        break;
                    }
                }
            }
        }
    }
}

void local_optimization_pro(Client_info &clientInfo, Site_Bandwidth_info siteBandwidthInfo, QoS_info qoSInfo, float up, float down, double *dream_cost)
{
    float up_limit = up;
    float down_limit = down;
    int up_bandwidth[200];   //记录每个边缘节点的0.95分位点处带宽
    int down_bandwidth[200]; //记录每个边缘节点的dowm_limit分位点处带宽
    /**
     * 更新0.95 和0.94分位点的带宽
     */
    for (int j = 0; j < siteBandwidthInfo.site_number; j++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[j];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);
        int tmp_up = ceil(clientInfo.clinet_timestamp_number * up_limit);
        up_bandwidth[j] = sort_list[tmp_up];
        int tmp_down = ceil(clientInfo.clinet_timestamp_number * down_limit);
        down_bandwidth[j] = sort_list[tmp_down];
    }

    /**
     * 开始遍历每个时刻，拿到每个时刻的要被分配的带宽
     */
    for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
    {

        for (int k = 0; k < siteBandwidthInfo.site_number; k++)
        {
            if (clientInfo.everyTime_client_info[i].cost[k] <= up_bandwidth[k] && clientInfo.everyTime_client_info[i].cost[k] >= down_bandwidth[k])
            {
                /**
                 * 当前节点是小于等于0.95,并且大于等于0.94的点，需要被分配出去
                 */
                //                cout<<up_bandwidth[k] <<" "<<down_bandwidth[k]<<endl;
                //                cout << "当前时刻：" << i << "--第" << k << "个边缘节点需要被分配，分配带宽为：" << clientInfo.everyTime_client_info[i].cost[k] << endl;
                /**
                 * 依次处理挂载在该节点上的每个流量
                 */

                for (int hand_back_index = 0; hand_back_index < clientInfo.everyTime_client_info[i].site_allo_list[k].size(); hand_back_index++)
                {
                    BandwidthInfo current_bandwidthIfo = clientInfo.everyTime_client_info[i].site_allo_list[k][hand_back_index];
                    /**
                     * 找到当前这个结构体能否分出去，如果能，就直接分，跳出循环，如果不能就往下走
                     */
                    //                    cout<<"第"<<k<<"个边缘节点的第"<<hand_back_index<<"个流为"<<current_bandwidthIfo.bandwidth<<endl;
                    ///遍历这个流量属于的那个客户端连接的所有边缘节点，是否有可以放入0.95以后，或者0.94以前。
                    int current_j = current_bandwidthIfo.clientNum;
                    /**
                     * 遍历这个客户节点连接的所有服务节点，是否有满足条件吧这个分过去的
                     */
                    for (int ii = 0; ii < clientInfo.every_client_max_connect[current_j]; ii++)
                    {
                        int tmp_k_index = (clientInfo.everyTime_client_info[i].circle[current_j] + ii) % clientInfo.every_client_max_connect[current_j];
                        int current_k = clientInfo.client_to_site[current_j][tmp_k_index];
                        if (current_k == k)
                            continue;
                        /**
                         * 找到一个满足条件的。当前该客户节点是大于0.95分位点的点。给他分配！
                         */
                        if (clientInfo.everyTime_client_info[i].cost[current_k] > up_bandwidth[current_k])
                        {
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= siteBandwidthInfo.site_bandwidth[current_k])
                            {
                                //访问的这个服务器节点满足要求，可以分配
                                if (up_bandwidth[k] > dream_cost[k])
                                {
                                    clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                    clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                    clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                    clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                    clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                    hand_back_index--; //因为erase完以后，总的size会减1，所以需要--

                                    //                                cout<<"这个流属于客户节点"<<current_bandwidthIfo.clientNum<<"可以分配给边缘节点------"<<current_k<<endl;
                                    //                                cout<<"要分配的这个结点的带宽为："<<clientInfo.everyTime_client_info[i].cost[current_k]<<endl;
                                    clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];
                                    break;
                                }
                            }
                        }
                        /**
                         * 当前客户节点是小于等于0.94分位点的点，给他分配！
                         */
                    }
                    if (clientInfo.everyTime_client_info[i].cost[k] <= dream_cost[k])
                    {
                        ///此时这个结点已经分到0.94以下，跳出
                        break;
                    }
                    if (hand_back_index == clientInfo.everyTime_client_info[i].site_allo_list[k].size() - 1)
                    {
                        /**
                         * 此时已经达到局部最小解了，需要调整后0.05分位点的值
                         */
                    }
                }
            }
        }
    }
}
int checkSum(Client_info &clientInfo, Site_Bandwidth_info siteBandwidthInfo, QoS_info qoSInfo,int time,int current_k,int *up_bandwidth,int *down_bandwidth){
    int left_sum=0;
    for(int i=0;i<siteBandwidthInfo.site_to_site[current_k].size();i++){
        int current_tmp_k=siteBandwidthInfo.site_to_site[current_k][i];
        if(clientInfo.everyTime_client_info[time].cost[current_tmp_k]<=down_bandwidth[current_tmp_k]){
            int tmp=0;
            tmp=down_bandwidth[current_tmp_k]-clientInfo.everyTime_client_info[time].cost[current_tmp_k];
            left_sum+=tmp;
        }else if(clientInfo.everyTime_client_info[time].cost[current_tmp_k]>up_bandwidth[current_tmp_k]){
            int tmp=0;
            tmp=siteBandwidthInfo.site_bandwidth[current_tmp_k]-clientInfo.everyTime_client_info[time].cost[current_tmp_k];
            left_sum+=tmp;
        }
    }
//    cout<<left_sum<<endl;
    int allo_bd=clientInfo.everyTime_client_info[time].cost[current_k]-down_bandwidth[current_k];
//    int max_bd=left_sum;
//    cout<<"所要分配出去的"<<allo_bd<<"所能分配出去的"<<left_sum<<endl;
    if(allo_bd>left_sum){
//        cout<<"分不了"<<endl;
        return 0;

    }
    else return 1;

}
void out_local_optimization(Client_info &clientInfo, Site_Bandwidth_info siteBandwidthInfo, QoS_info qoSInfo, float up, float down)
{
    float up_limit = up;     // 0.95
    float down_limit = down; // 0.70
    int nine_five_bandwidth[200];
    int up_bandwidth[200];   //记录每个边缘节点的0.95分位点处带宽
    int down_bandwidth[200]; //记录每个边缘节点的dowm_limit分位点处带宽


    for (int j = 0; j < siteBandwidthInfo.site_number; j++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[j];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);
        int tmp_up = ceil(clientInfo.clinet_timestamp_number * up_limit) - 1;
        up_bandwidth[j] = sort_list[tmp_up];
        int tmp_upp = ceil(clientInfo.clinet_timestamp_number * 0.95) - 1;
        nine_five_bandwidth[j] = sort_list[tmp_upp];
        int tmp_down = ceil(clientInfo.clinet_timestamp_number * down_limit) - 1;
        down_bandwidth[j] = sort_list[tmp_down];
    }
    stack<Redo_Log> redo_log;
    for (int k = 0; k < siteBandwidthInfo.site_number; k++)
    {
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            if (clientInfo.everyTime_client_info[i].cost[k] > up_bandwidth[k])
            {
//                int left_sum=checkSum(clientInfo,siteBandwidthInfo,qoSInfo,i,k,up_bandwidth,down_bandwidth);
                //当前该节点是大于0.95分位点的结点。对其进行处理
//                if(left_sum==0)continue;
                if (!redo_log.empty())
                {
                    cout << "咋回事，栈非空！！" << endl;
                    throw new exception;
                };
                /**
                 * 对当前时刻进行预分配，看看预分配的结果能否实现调整。
                 * 尝试能否将这个极端分配节点移到0.95前面去；
                 */

                //                CurrentTime_client_info tmp_currentTime_client_info;
                //                tmp_currentTime_client_info.init();
                //                tmp_currentTime_client_info.copy(clientInfo.everyTime_client_info[i]);
                int is_allo = 0; //用于标识该节点在预分配过程中是否可以完成分配。
                for (int gb_hand_back_index = 0; gb_hand_back_index < clientInfo.everyTime_client_info[i].site_allo_list[k].size(); gb_hand_back_index++)
                {
                    BandwidthInfo tmp_current_bandwidthInfo = clientInfo.everyTime_client_info[i].site_allo_list[k][gb_hand_back_index];
                    ///尝试把结构体分出去。
                    int tmp_current_j = tmp_current_bandwidthInfo.clientNum;
                    for (int tmp_ii = 0; tmp_ii < clientInfo.every_client_max_connect[tmp_current_j]; tmp_ii++)
                    {

                        int tmp_tmp_k_index = (clientInfo.everyTime_client_info[i].circle[tmp_current_j] + tmp_ii) % clientInfo.every_client_max_connect[tmp_current_j];
                        int tmp_current_k = clientInfo.client_to_site[tmp_current_j][tmp_tmp_k_index];
                        if (k == tmp_current_k)
                            continue;
                        if (clientInfo.everyTime_client_info[i].cost[tmp_current_k] > up_bandwidth[tmp_current_k])
                        {
                            ///这是一个大于0.95分位点的点，尝试分配给它
                            if (clientInfo.everyTime_client_info[i].cost[tmp_current_k] + tmp_current_bandwidthInfo.bandwidth <= siteBandwidthInfo.site_bandwidth[tmp_current_k])
                            {
                                clientInfo.everyTime_client_info[i].cost[tmp_current_k] += tmp_current_bandwidthInfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= tmp_current_bandwidthInfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[tmp_current_bandwidthInfo.streamNum][tmp_current_bandwidthInfo.clientNum] = tmp_current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + gb_hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[tmp_current_k].push_back(tmp_current_bandwidthInfo);
                                gb_hand_back_index--; //因为erase完以后，总的size会减1，所以需要--
                                clientInfo.everyTime_client_info[i].circle[tmp_current_j] = (tmp_tmp_k_index + 1) % clientInfo.every_client_max_connect[tmp_current_j];

                                Redo_Log element;
                                element.k = k;
                                element.current_k = tmp_current_k;
                                element.bandwidth = tmp_current_bandwidthInfo.bandwidth;
                                element.clientNum = tmp_current_bandwidthInfo.clientNum;
                                element.streamNum = tmp_current_bandwidthInfo.streamNum;
                                redo_log.push(element);
                                break;
                            }
                        }
                        else if (clientInfo.everyTime_client_info[i].cost[tmp_current_k] < down_bandwidth[tmp_current_k])
                        {
                            ///这是一个小于0.94分位点的点，尝试分配给它
                            if (clientInfo.everyTime_client_info[i].cost[tmp_current_k] + tmp_current_bandwidthInfo.bandwidth <= down_bandwidth[tmp_current_k])
                            {
                                clientInfo.everyTime_client_info[i].cost[tmp_current_k] += tmp_current_bandwidthInfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= tmp_current_bandwidthInfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[tmp_current_bandwidthInfo.streamNum][tmp_current_bandwidthInfo.clientNum] = tmp_current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + gb_hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[tmp_current_k].push_back(tmp_current_bandwidthInfo);
                                gb_hand_back_index--;
                                clientInfo.everyTime_client_info[i].circle[tmp_current_j] = (tmp_tmp_k_index + 1) % clientInfo.every_client_max_connect[tmp_current_j];

                                Redo_Log element;
                                element.k = k;
                                element.current_k = tmp_current_k;
                                element.bandwidth = tmp_current_bandwidthInfo.bandwidth;
                                element.clientNum = tmp_current_bandwidthInfo.clientNum;
                                element.streamNum = tmp_current_bandwidthInfo.streamNum;
                                redo_log.push(element);
                                break;
                            }
                        }
                        //
                    }
                    if (clientInfo.everyTime_client_info[i].cost[k] <= up_bandwidth[k])
                    {
                        ///此时这个结点已经分到0.94以下，跳出
                        is_allo = 1; //表示这个结点可以放到前面去！
                        break;
                    }
                    if (gb_hand_back_index == clientInfo.everyTime_client_info[i].site_allo_list[k].size() - 1)
                    {
                        is_allo = 0;
                    }
                }
                if (is_allo == 1)
                {
                    /**
                     * 该节点可以分配，那就这么做吧
                     */
                    //                    clientInfo.everyTime_client_info[i].copy(tmp_currentTime_client_info);
                    //                    cout<<"可以执行，清空栈"<<endl;
                    while (!redo_log.empty())
                    {
                        redo_log.pop();
                    }
                    /**
                     * 该节点已经分配到0.94的范围了，这时候需要重新调整一下第k个边缘节点的0.95分位点
                     */
                }
                else if (is_allo == 0)
                {
                    /**
                     * 不可以这么做，执行日志回访操作
                     */
                    //                     cout<<"不可以执行，进行回放"<<endl;
                    while (!redo_log.empty())
                    {

                        clientInfo.everyTime_client_info[i].cost[redo_log.top().current_k] -= redo_log.top().bandwidth;
                        clientInfo.everyTime_client_info[i].cost[redo_log.top().k] += redo_log.top().bandwidth;
                        clientInfo.everyTime_client_info[i].allo_stream_client_toSite[redo_log.top().streamNum][redo_log.top().clientNum] = redo_log.top().k;
                        clientInfo.everyTime_client_info[i].site_allo_list[k].push_back(clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k][clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].size() - 1]);
                        clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k]) + (clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].size() - 1));
                        //                         clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k])+gb_hand_back_index);
                        //                         clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].push_back(tmp_current_bandwidthInfo);
                        redo_log.pop();
                    }
                }
            }
        }
        //这个结点已经全部处理完了，可以重新计算upbandwidth了
        int t_sort_list[clientInfo.clinet_timestamp_number];
        for (int t_i = 0; t_i < clientInfo.clinet_timestamp_number; t_i++)
        {
            t_sort_list[t_i] = clientInfo.everyTime_client_info[t_i].cost[k];
        }
        sort(t_sort_list, t_sort_list + clientInfo.clinet_timestamp_number);
        int ttmp_up = ceil(clientInfo.clinet_timestamp_number * up_limit) - 1;
        up_bandwidth[k] = t_sort_list[ttmp_up];
        int ttmp_down = ceil(clientInfo.clinet_timestamp_number * down_limit) - 1;
        down_bandwidth[k] = t_sort_list[ttmp_down];
    }
    cout << "out_local" << endl;
    //    check_error(clientInfo,siteBandwidthInfo,qoSInfo);
}

//////////////////////////////////////////////////////////////////////////////////////
// 坤坤代码开始：初始解相关函数
//////////////////////////////////////////////////////////////////////////////////////

template <typename T>
bool _any(T *start, int n)
{
    for (int i = 0; i < n; i++, start++)
    {
        if (*start)
        {
            return true;
        }
    }
    return false;
}

void _full(int *start, int n, int value)
{
    for (int i = 0; i < n; i++, start++)
    {
        *start = value;
    }
}

template <typename T>
T &_rand_choise(vector<T> &vec)
{
    return vec[rand() % vec.size()];
}

int _sum(int *start, int n)
{
    int ans = 0;
    for (int i = 0; i < n; i++, start++)
    {
        ans += (*start);
    }
    return ans;
};

class _HeapNode
{
public:
    int t;
    int heap_idx;
    int value;
    _HeapNode(int t, int value)
    {
        this->t = t;
        this->value = value;
    }
};

bool _heap_node_cmp(_HeapNode *x, _HeapNode *y)
{
    return x->value < y->value;
};

class LargestUpdater
{
public:
    vector<_HeapNode *> heap_vec;
    vector<_HeapNode *> t_index_vec;
    int size;

    LargestUpdater(vector<int> &value_arr)
    {
        int T = value_arr.size();
        this->size = T;
        this->heap_vec.reserve(T);
        this->t_index_vec.reserve(T);

        for (int t = 0; t < T; t++)
        {
            _HeapNode *node = new _HeapNode(t, value_arr[t]);
            this->heap_vec.push_back(node);
            this->t_index_vec.push_back(node);
        }

        make_heap(this->heap_vec.begin(), this->heap_vec.end(), _heap_node_cmp);

        for (int _i = 0; _i < T; _i++)
        {
            this->heap_vec[_i]->heap_idx = _i;
        }
    }

    _HeapNode *head()
    {
        if (this->size)
        {
            return heap_vec[0];
        }
        else
        {
            return NULL;
        }
    }

    _HeapNode *at(int t)
    {
        return this->t_index_vec[t];
    }

    void pop()
    {
        if (this->size)
        {
            this->_swap_node(heap_vec[0], heap_vec[--this->size]);
            this->_adjust_lower(heap_vec[0]);
        }
    }

    void decrease(int t, int diff)
    {
        if (diff < 0)
        {
            cout << "ERROR: unsupport increase value" << endl;
            throw exception();
        }

        _HeapNode *node = this->t_index_vec[t];
        if (node->heap_idx >= this->size)
        {
            cout << "ERROR: unsupport update poppid value" << endl;
            throw exception();
        }

        node->value -= diff;
        this->_adjust_lower(node);
    }

private:
    void _adjust_lower(_HeapNode *target_node)
    {
        _HeapNode *left_child = target_node;
        _HeapNode *right_child = target_node;

        int left_child_idx = target_node->heap_idx * 2 + 1;
        int right_child_idx = target_node->heap_idx * 2 + 2;

        if (left_child_idx < this->size)
        {
            left_child = this->heap_vec[left_child_idx];
        }
        if (right_child_idx < this->size)
        {
            right_child = this->heap_vec[right_child_idx];
        }

        if (left_child->value > right_child->value)
        {
            if (left_child->value > target_node->value)
            {
                this->_swap_node(target_node, left_child);
                this->_adjust_lower(target_node);
            }
        }
        else
        {
            if (right_child->value > target_node->value)
            {
                this->_swap_node(target_node, right_child);
                this->_adjust_lower(target_node);
            }
        }
    }
    void _swap_node(_HeapNode *n1, _HeapNode *n2)
    {
        this->heap_vec[n1->heap_idx] = n2;
        this->heap_vec[n2->heap_idx] = n1;
        int _tmp_idx = n1->heap_idx;
        n1->heap_idx = n2->heap_idx;
        n2->heap_idx = _tmp_idx;
    }
};

class SiteLargestTDemandManager //用于维护站点大流量排序
{
public:
    vector<LargestUpdater *> site_largest_tdemand_updater;
    int site_full_demand_count[135] = {0}; //站点可以被需求量打满的个数
    Site_Bandwidth_info *siteInfo;

    SiteLargestTDemandManager(int min_stream, Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
    {
        this->siteInfo = &siteInfo;

        int T = clientInfo.clinet_timestamp_number;
        int N = siteInfo.site_number;
        int M = clientInfo.client_number;

        vector<vector<int>> site_tdemand_matrix;
        site_tdemand_matrix.clear();
        for (int site_id = 0; site_id < N; site_id++)
        {
            vector<int> _tmp_vec;
            _tmp_vec.reserve(T);
            for (int t = 0; t < T; t++)
            {
                _tmp_vec.push_back(0);
            }
            site_tdemand_matrix.push_back(_tmp_vec);
        }

        for (int t = 0; t < T; t++)
        {
            CurrentTime_client_info &current_client_info = clientInfo.everyTime_client_info[t];
            int P = current_client_info.streamNumber;
            for (int client_id = 0; client_id < M; client_id++)
            {
                int client_large_deamnd_sum = 0;
                for (int stream_id = 0; stream_id < P; stream_id++)
                {
                    int demand_bw = current_client_info.current_stream_client_bandwidth[stream_id][client_id];
                    if (demand_bw > min_stream)
                    {
                        client_large_deamnd_sum += demand_bw;
                    }
                }

                for (auto &site_id : clientInfo.client_to_site[client_id])
                {
                    site_tdemand_matrix[site_id][t] += client_large_deamnd_sum;
                }
            }

            for (int site_id = 0; site_id < N; site_id++)
            {
                if (site_tdemand_matrix[site_id][t] >= siteInfo.site_bandwidth[site_id])
                {
                    this->site_full_demand_count[site_id]++;
                }
            }
        }

        for (int site_id = 0; site_id < N; site_id++)
        {
            this->site_largest_tdemand_updater.push_back(new LargestUpdater(site_tdemand_matrix[site_id]));
        }
    };

    void next(int &t, int &site_id, int &largest_demand)
    {
        t = -1;
        site_id = -1;
        largest_demand = -1;

        int min_cout = 100000;
        for (int _site_id = 0; _site_id < this->site_largest_tdemand_updater.size(); _site_id++)
        {
            int _full_demand_count = this->site_full_demand_count[_site_id];
            if ((_full_demand_count != -1) && (_full_demand_count < min_cout))
            {
                min_cout = _full_demand_count;
                site_id = _site_id;
            }
        }

        if (site_id != -1)
        {
            LargestUpdater *largest_updater = this->site_largest_tdemand_updater[site_id];
            _HeapNode *node = largest_updater->head();
            t = node->t;
            largest_demand = node->value;

            if (largest_demand >= this->siteInfo->site_bandwidth[site_id])
            {
                this->site_full_demand_count[site_id]--;
            }

            largest_updater->pop();
        }
    }

    void clear_demand_heap(int site_id)
    {
        this->site_full_demand_count[site_id] = -1;
        this->site_largest_tdemand_updater[site_id] = NULL;
    }

    void decrease_demand_heap(int t, int (&site_demand_decrement)[135])
    {
        for (int site_id = 0; site_id < this->site_largest_tdemand_updater.size(); site_id++)
        {
            LargestUpdater *largest_updater = this->site_largest_tdemand_updater[site_id];
            if ((!largest_updater) || (!site_demand_decrement[site_id]))
            {
                continue;
            }

            int old_demand = largest_updater->at(t)->value;
            int new_demand = old_demand - site_demand_decrement[site_id];
            int site_bw_upper = this->siteInfo->site_bandwidth[site_id];
            // 如果旧的带宽需求大于站点带宽上限而新的需求小于带宽上限，则可打满次数减一
            if ((old_demand >= site_bw_upper) && (new_demand < site_bw_upper))
            {
                this->site_full_demand_count[site_id]--;
            }

            largest_updater->decrease(t, site_demand_decrement[site_id]);
        }
    }
};

class TAssignState //用来记录t时刻的带宽分配状态（未分配流量、站点剩余带宽、极端分配节点）
{
public:
    int site_bw_remained_arr[135] = {0};
    bool site_big_bw_flag_arr[135] = {false};

    TAssignState(CurrentTime_client_info &current_client_info, Site_Bandwidth_info &siteBandwidthInfo)
    {
        for (int site_id = 0; site_id < siteBandwidthInfo.site_number; site_id++)
        {
            this->site_bw_remained_arr[site_id] = siteBandwidthInfo.site_bandwidth[site_id];
        };
    };
};

bool _bw_cmp(BandwidthInfo &x, BandwidthInfo &y)
{
    return x.bandwidth > y.bandwidth; //定义降序排序（从大到小）
}

double _score(int cost, int base_cost, int site_bw_upper)
{
    if (cost <= base_cost)
    {
        return base_cost;
    }
    else
    {
        double diff = (cost - base_cost);
        return diff * diff / site_bw_upper + cost;
    }
}

void sort_demand_within_everytime(Client_info &clientInfo, Site_Bandwidth_info &siteBandwidthInfo, QoS_info &qoSInfo)
{
    int M = clientInfo.client_number;
    for (auto &current_client_info : clientInfo.everyTime_client_info)
    {
        int bw_index = 0;
        int stream_num = current_client_info.streamNumber;
        for (int stream_id = 0; stream_id < stream_num; stream_id++)
        {
            for (int client_id = 0; client_id < M; client_id++)
            {
                current_client_info.bandwidthInfo[bw_index].clientNum = client_id;
                current_client_info.bandwidthInfo[bw_index].streamNum = stream_id;
                current_client_info.bandwidthInfo[bw_index].bandwidth = current_client_info.current_stream_client_bandwidth[stream_id][client_id];
                bw_index++;
            }
        }
        sort(current_client_info.bandwidthInfo, current_client_info.bandwidthInfo + bw_index, _bw_cmp);
    }
}

void radical_assign(int (&site_demand_decrement)[135], int t, int site_id, int largest_demand, TAssignState *tassign_state, Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
{
    tassign_state->site_big_bw_flag_arr[site_id] = true;
    CurrentTime_client_info &current_client_info = clientInfo.everyTime_client_info[t];
    int site_remained_bw = tassign_state->site_bw_remained_arr[site_id];

    for (auto &bw_info : current_client_info.bandwidthInfo) //已经是按照带宽需求从大到小排序的
    {
        int demand_bw = bw_info.bandwidth;
        if (!demand_bw)
        {
            break;
        }
        if (site_remained_bw < demand_bw)
        {
            continue;
        }

        int client_id = bw_info.clientNum;
        if (!qoSInfo.QoS[site_id][client_id])
        { //不可达，跳过
            continue;
        }

        int stream_id = bw_info.streamNum;
        // 如果该流已经被分配过了，则跳过
        if (current_client_info.allo_stream_client_toSite[stream_id][client_id] != -1)
        {
            continue;
        }

        current_client_info.allo_stream_client_toSite[stream_id][client_id] = site_id;
        current_client_info.cost[site_id] += demand_bw;
        current_client_info.site_allo_list[site_id].push_back(bw_info);

        site_remained_bw -= demand_bw;

        for (auto &adjacent_site_id : clientInfo.client_to_site[client_id])
        {
            if (!(tassign_state->site_big_bw_flag_arr[adjacent_site_id]))
            {
                site_demand_decrement[adjacent_site_id] += demand_bw;
            }
        }
    }

    tassign_state->site_bw_remained_arr[site_id] = site_remained_bw;
}

void low_score_first_assign(int t, TAssignState *tassign_state, int base_cost, Client_info &clientInfo, Site_Bandwidth_info &siteInfo)
{
    CurrentTime_client_info &current_client_info = clientInfo.everyTime_client_info[t];
    int N = siteInfo.site_number;
    double site_score_arr[N];
    for (int site_id = 0; site_id < N; site_id++)
    {
        site_score_arr[site_id] = _score(current_client_info.cost[site_id], base_cost, siteInfo.site_bandwidth[site_id]);
    }

    for (auto &bw_info : current_client_info.bandwidthInfo) //已经是按照带宽需求从大到小排序的
    {
        if (!bw_info.bandwidth)
        {
            break;
        }
        int client_id = bw_info.clientNum;
        int stream_id = bw_info.streamNum;
        int demand_bw = bw_info.bandwidth;

        // 如果该流已经被分配过了，则跳过
        if (current_client_info.allo_stream_client_toSite[stream_id][client_id] != -1)
        {
            continue;
        }

        int selected_site_id = -1;
        double _min_score_increase = 10e100;
        for (auto &site_id : clientInfo.client_to_site[client_id])
        {
            if (siteInfo.site_bandwidth[site_id] < demand_bw)
            {
                continue;
            }
            double score_increase = _score(current_client_info.cost[site_id] + demand_bw, base_cost, siteInfo.site_bandwidth[site_id]) - site_score_arr[site_id];
            if (score_increase < _min_score_increase)
            {
                selected_site_id = site_id;
                _min_score_increase = score_increase;
            }
        }

        if (selected_site_id == -1)
        {
            //找不到合适的site_id，这种情况不应该出现，可能是数据中出现了无解的情况
            cout << "ERROR: selected_site_id == -1" << endl;
            throw exception();
        }

        current_client_info.allo_stream_client_toSite[stream_id][client_id] = selected_site_id;
        current_client_info.cost[selected_site_id] += demand_bw;
        current_client_info.site_allo_list[selected_site_id].push_back(bw_info);

        tassign_state->site_bw_remained_arr[selected_site_id] -= demand_bw;

        site_score_arr[selected_site_id] += _min_score_increase;
    }
}

void process_overflow(int t, TAssignState *tassign_state, Client_info &clientInfo, Site_Bandwidth_info &siteBandwidthInfo)
{
    CurrentTime_client_info &current_client_info = clientInfo.everyTime_client_info[t];
    int N = siteBandwidthInfo.site_number;

    bool not_finish = true;
    while (not_finish)
    {
        not_finish = false;
        for (int site_id = 0; site_id < N; site_id++)
        {
            if (current_client_info.cost[site_id] > siteBandwidthInfo.site_bandwidth[site_id])
            {
                not_finish = true;
                vector<BandwidthInfo> &site_allo_vec = current_client_info.site_allo_list[site_id];
                sort(site_allo_vec.begin(), site_allo_vec.end(), _bw_cmp);

                int allo_idx = site_allo_vec.size() - 1;
                while ((allo_idx >= 0) && (current_client_info.cost[site_id] > siteBandwidthInfo.site_bandwidth[site_id]))
                {
                    BandwidthInfo minist_bw = site_allo_vec[allo_idx]; //这里不要用引用
                    int client_id = minist_bw.clientNum;
                    int transfer_site_id = -1;
                    for (int _i = 0; _i < 8; _i++)
                    {
                        int _site_id = _rand_choise(clientInfo.client_to_site[client_id]);
                        if (_site_id != site_id)
                        {
                            transfer_site_id = _site_id;
                            break;
                        }
                    }

                    if (transfer_site_id != -1)
                    {
                        int demand_bw = minist_bw.bandwidth;
                        int stream_id = minist_bw.streamNum;

                        current_client_info.allo_stream_client_toSite[stream_id][client_id] = transfer_site_id;
                        current_client_info.cost[transfer_site_id] += demand_bw;
                        current_client_info.cost[site_id] -= demand_bw;

                        current_client_info.site_allo_list[transfer_site_id].push_back(minist_bw);

                        swap(site_allo_vec.back(), site_allo_vec[allo_idx]); //先和最后一个元素交换位置，再把它删掉
                        site_allo_vec.pop_back();

                        tassign_state->site_bw_remained_arr[transfer_site_id] -= demand_bw;
                        tassign_state->site_bw_remained_arr[site_id] += demand_bw;
                    }
                    allo_idx--;
                }
            }
        }
    }
}
void init_site_to_site(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo){
    siteInfo.site_to_site.clear();
    for(int i=0;i<siteInfo.site_number;i++){
        vector<int> tmp;
        tmp.clear();
        siteInfo.site_to_site.push_back(tmp);
    }
    for(int k=0;k<siteInfo.site_number;k++){
        int a[135]={0};
        for(int j=0;j<siteInfo.site_to_client[k].size();j++){
            int current_j=siteInfo.site_to_client[k][j];
            for(int w=0;w<clientInfo.client_to_site[current_j].size();w++){
                int current_site=clientInfo.client_to_site[current_j][w];
                if(a[current_site]==0){
                    a[current_site]=1;
                    if(current_site==k)continue;
                    siteInfo.site_to_site[k].push_back(current_site);
                }
            }
        }
    }
//
}
void init_solution(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
{
    int min_stream = 0; //小流量阈值，小于该值的都作为小流量

    sort_demand_within_everytime(clientInfo, siteInfo, qoSInfo);
    SiteLargestTDemandManager site_largest_tdemand_manager(min_stream, clientInfo, siteInfo, qoSInfo);
    vector<TAssignState *> assign_states;

    for (auto &current_client_info : clientInfo.everyTime_client_info)
    {
        assign_states.push_back(new TAssignState(current_client_info, siteInfo));
    }

    int N = siteInfo.site_number;
    int T = clientInfo.clinet_timestamp_number;

    int quantile_index = ceil(0.95 * T) - 1;
    int big_bw_num = (T - (quantile_index + 1));
    int site_big_bw_remained_count[135] = {0};

    for (int site_id = 0; site_id < N; site_id++)
    {
        if (siteInfo.every_site_max_connect[site_id] > 0)
        {
            site_big_bw_remained_count[site_id] = big_bw_num;
        }
    }

    int t, site_id, largest_demand;
    site_largest_tdemand_manager.next(t, site_id, largest_demand);

    /**
     * 分配后0.05
     */
    int site_demand_decrement[135]; //分配一个极端节点后，同时刻其他节点的带宽量会降低，这里记录的是降低的量，大于等于0
    while (t != -1)
    {
        if (!largest_demand) //如果服务器的最大请求量为0，则后面就没必要再给其分配极端节点了
        {
            site_largest_tdemand_manager.clear_demand_heap(site_id);
        }
        else if (site_big_bw_remained_count[site_id])
        {
            _full(site_demand_decrement, 135, 0);
            ///分配极端分配节点
            /**
             *
             */
            radical_assign(site_demand_decrement, t, site_id, largest_demand, assign_states[t], clientInfo, siteInfo, qoSInfo);

            site_big_bw_remained_count[site_id]--;

            if (!site_big_bw_remained_count[site_id]) // 大流量计数全部用完，所以清空堆，避免无用循环
            {
                site_largest_tdemand_manager.clear_demand_heap(site_id);
            }

            site_largest_tdemand_manager.decrease_demand_heap(t, site_demand_decrement);
        }
        site_largest_tdemand_manager.next(t, site_id, largest_demand);
    }

    /**
     * 开始分前0.95
     */
    int base_cost = qoSInfo.base_cost;
    for (int t = 0; t < T; t++)
    {
        low_score_first_assign(t, assign_states[t], base_cost, clientInfo, siteInfo);
        process_overflow(t, assign_states[t], clientInfo, siteInfo);
    }
}

//////////////////////////////////////////////////////////////////////////////////////
// 坤坤代码结束：初始解相关函数
//////////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////
// 坤坤代码开始：优化解相关函数
//////////////////////////////////////////////////////////////////////////////////////

double show_score(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
{
    float quantile = 0.95;
    float up = 0.95;
    float down = 0.90;
    double score = 0.0;
    for (int site_id = 0; site_id < siteInfo.site_number; site_id++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[site_id];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);

        int _quantile_idx = ceil(clientInfo.clinet_timestamp_number * quantile) - 1;
        int nine_five_bandwidth = sort_list[_quantile_idx];

        score += _score(nine_five_bandwidth, qoSInfo.base_cost, siteInfo.site_bandwidth[site_id]);
    }

    cout << "score:" << int(score) << endl;
    return score;
}

double local_optimization(Client_info &clientInfo, Site_Bandwidth_info &siteBandwidthInfo, QoS_info &qoSInfo, float up_quantile, float down_quantile)
{
    int nine_five_bandwidth[135];
    int up_bandwidth[135];   //记录每个边缘节点的0.95分位点处带宽
    int down_bandwidth[135]; //记录每个边缘节点的dowm_limit分位点处带宽
    double score = 0.0;

    for (int site_id = 0; site_id < siteBandwidthInfo.site_number; site_id++)
    {
        int sort_list[clientInfo.clinet_timestamp_number];
        for (int i = 0; i < clientInfo.clinet_timestamp_number; i++)
        {
            sort_list[i] = clientInfo.everyTime_client_info[i].cost[site_id];
        }
        sort(sort_list, sort_list + clientInfo.clinet_timestamp_number);

        int _quantile_idx = ceil(clientInfo.clinet_timestamp_number * 0.95) - 1;
        nine_five_bandwidth[site_id] = sort_list[_quantile_idx];

        int _up_idx = ceil(clientInfo.clinet_timestamp_number * up_quantile) - 1;
        up_bandwidth[site_id] = sort_list[_up_idx];

        int _down_idx = ceil(clientInfo.clinet_timestamp_number * down_quantile) - 1;
        down_bandwidth[site_id] = sort_list[_down_idx];

        score += _score(nine_five_bandwidth[site_id], qoSInfo.base_cost, siteBandwidthInfo.site_bandwidth[site_id]);
    }
    cout << "[local_optimization] current score:" << score << endl;

    int T = clientInfo.clinet_timestamp_number;
    int N = siteBandwidthInfo.site_number;
//    stack<Redo_Log> redo_log;
    for (int i = 0; i < T; i++)
    {
        for (int k = 0; k < N; k++)
        {
            if (clientInfo.everyTime_client_info[i].cost[k] <= up_bandwidth[k] && clientInfo.everyTime_client_info[i].cost[k] >= down_bandwidth[k]&& clientInfo.everyTime_client_info[i].cost[k]>qoSInfo.base_cost)
            {
//                if (!redo_log.empty())
//                {
//                    cout << "咋回事，栈非空！！" << endl;
//                    throw new exception;
//                };
                int is_allo = 0;
                for (int hand_back_index = 0; hand_back_index < clientInfo.everyTime_client_info[i].site_allo_list[k].size(); hand_back_index++)
                {
                    BandwidthInfo current_bandwidthIfo = clientInfo.everyTime_client_info[i].site_allo_list[k][hand_back_index];
                    /**
                     * 找到当前这个结构体能否分出去，如果能，就直接分，跳出循环，如果不能就往下走
                     */
                    //                    cout<<"第"<<k<<"个边缘节点的第"<<hand_back_index<<"个流为"<<current_bandwidthIfo.bandwidth<<endl;
                    ///遍历这个流量属于的那个客户端连接的所有边缘节点，是否有可以放入0.95以后，或者0.94以前。
                    int current_j = current_bandwidthIfo.clientNum;
                    /**
                     * 遍历这个客户节点连接的所有服务节点，是否有满足条件吧这个分过去的
                     */
                    for (int ii = 0; ii < clientInfo.every_client_max_connect[current_j]; ii++)
                    {
                        int tmp_k_index = (clientInfo.everyTime_client_info[i].circle[current_j] + ii) % clientInfo.every_client_max_connect[current_j];
                        int current_k = clientInfo.client_to_site[current_j][tmp_k_index];
                        if (current_k == k)
                            continue;
                        /**
                         * 找到一个满足条件的。当前该客户节点是大于0.95分位点的点。给他分配！
                         */
                        if(clientInfo.everyTime_client_info[i].cost[current_k]<qoSInfo.base_cost){
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= qoSInfo.base_cost&&clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth<=siteBandwidthInfo.site_bandwidth[current_k])
                            {
                                clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                hand_back_index--;
                                clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];

                                /**
                                 * 加入回放栈，
                                 */
//                                Redo_Log element;
//                                element.k = k;
//                                element.current_k = current_k;
//                                element.bandwidth = current_bandwidthIfo.bandwidth;
//                                element.clientNum = current_bandwidthIfo.clientNum;
//                                element.streamNum = current_bandwidthIfo.streamNum;
//                                redo_log.push(element);
                                break;
                                //                                }
                            }
                        }else if (clientInfo.everyTime_client_info[i].cost[current_k] > up_bandwidth[current_k])
                        {
                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= siteBandwidthInfo.site_bandwidth[current_k])
                            {
                                //访问的这个服务器节点满足要求，可以分配

                                clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                hand_back_index--; //因为erase完以后，总的size会减1，所以需要--

                                //                                cout<<"这个流属于客户节点"<<current_bandwidthIfo.clientNum<<"可以分配给边缘节点------"<<current_k<<endl;
                                //                                cout<<"要分配的这个结点的带宽为："<<clientInfo.everyTime_client_info[i].cost[current_k]<<endl;
                                clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];

//                                Redo_Log element;
//                                element.k = k;
//                                element.current_k = current_k;
//                                element.bandwidth = current_bandwidthIfo.bandwidth;
//                                element.clientNum = current_bandwidthIfo.clientNum;
//                                element.streamNum = current_bandwidthIfo.streamNum;
//                                redo_log.push(element);
                                break;
                            }
                        }
                            /**
                             * 当前客户节点是小于等于0.94分位点的点，给他分配！
                             */
                        else if (clientInfo.everyTime_client_info[i].cost[current_k] < up_bandwidth[current_k]-100&&clientInfo.everyTime_client_info[i].cost[current_k]>=qoSInfo.base_cost)
                        {

                            if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth < up_bandwidth[current_k]-100&&clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth<=siteBandwidthInfo.site_bandwidth[current_k])
                            {
                                clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
                                clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
                                clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
                                clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
                                hand_back_index--;
                                clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];

                                /**
                                 * 加入回放栈，
                                 */
//                                Redo_Log element;
//                                element.k = k;
//                                element.current_k = current_k;
//                                element.bandwidth = current_bandwidthIfo.bandwidth;
//                                element.clientNum = current_bandwidthIfo.clientNum;
//                                element.streamNum = current_bandwidthIfo.streamNum;
//                                redo_log.push(element);
                                break;
                                //                                }
                            }
                        }
                    }
                    if (clientInfo.everyTime_client_info[i].cost[k] <= down_bandwidth[k])
                    {
                        ///此时这个结点已经分到0.94以下，跳出
                        is_allo = 1;
                        break;
                    }

                }
                if (is_allo == 1)
                {
                    /**
                     * 该节点可以分配，那就这么做吧
                     */
                    //                    clientInfo.everyTime_client_info[i].copy(tmp_currentTime_client_info);
                    //                    cout<<"可以执行，清空栈"<<endl;
//                    while (!redo_log.empty())
//                    {
//                        redo_log.pop();
//                    }
                    /**
                     * 该节点已经分配到0.94的范围了，这时候需要重新调整一下第k个边缘节点的0.95分位点
                     */
                }
                else if (is_allo == 0)
                {
                    /**
                     * 不可以这么做，执行日志回访操作
                     */
                    //                     cout<<"不可以执行，进行回放"<<endl;
//                    while (!redo_log.empty())
//                    {
//
//                        clientInfo.everyTime_client_info[i].cost[redo_log.top().current_k] -= redo_log.top().bandwidth;
//                        clientInfo.everyTime_client_info[i].cost[redo_log.top().k] += redo_log.top().bandwidth;
//                        clientInfo.everyTime_client_info[i].allo_stream_client_toSite[redo_log.top().streamNum][redo_log.top().clientNum] = redo_log.top().k;
//                        clientInfo.everyTime_client_info[i].site_allo_list[k].push_back(clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k][clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].size() - 1]);
//                        clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k]) + (clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].size() - 1));
//                        redo_log.pop();
//                    }
                }
            }
        }
    }
    return score;
}

void refine_solution(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
{
    float up_quantile = 0.95;
    float down_quantile = 0.944;
    double sum=0;


    int lunci=20;
    while(lunci--){
        int max_first_local_opt_iter = 80;
        for (int _i = 0; _i < max_first_local_opt_iter; _i++)
        {

            cout << "i:" << _i << endl;
            double tmp=local_optimization(clientInfo, siteInfo, qoSInfo, up_quantile, down_quantile);
            if(sum==tmp){
                break;
            }else sum=tmp;
        }
//        endTime = clock(); //计时结束
//        cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        clock_t endtime=clock();
        if((double)(endtime - startTime) / CLOCKS_PER_SEC>200){
//            cout<<endtime<<endl;
            cout << "The run time is: " << (double)(endtime - startTime) / CLOCKS_PER_SEC << "s" << endl;
            break;
        }

        if(lunci!=0)out_local_optimization(clientInfo, siteInfo, qoSInfo, up_quantile, 0.945);
    }



//                             if (clientInfo.everyTime_client_info[i].cost[current_k] + current_bandwidthIfo.bandwidth <= down_bandwidth[current_k])
//                             {
//                                 clientInfo.everyTime_client_info[i].cost[current_k] += current_bandwidthIfo.bandwidth;
//                                 clientInfo.everyTime_client_info[i].cost[k] -= current_bandwidthIfo.bandwidth;
//                                 clientInfo.everyTime_client_info[i].allo_stream_client_toSite[current_bandwidthIfo.streamNum][current_bandwidthIfo.clientNum] = current_k;
//                                 clientInfo.everyTime_client_info[i].site_allo_list[k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[k]) + hand_back_index);
//                                 clientInfo.everyTime_client_info[i].site_allo_list[current_k].push_back(current_bandwidthIfo);
//                                 hand_back_index--;
//                                 clientInfo.everyTime_client_info[i].circle[current_j] = (tmp_k_index + 1) % clientInfo.every_client_max_connect[current_j];

//                                 /**
//                                  * 加入回放栈，
//                                  */
//                                 Redo_Log element;
//                                 element.k = k;
//                                 element.current_k = current_k;
//                                 element.bandwidth = current_bandwidthIfo.bandwidth;
//                                 element.clientNum = current_bandwidthIfo.clientNum;
//                                 element.streamNum = current_bandwidthIfo.streamNum;
//                                 redo_log.push(element);
//                                 break;
//                                 //                                }
//                             }
//                         }
//                     }
//                     if (clientInfo.everyTime_client_info[i].cost[k] <= down_bandwidth[k])
//                     {
//                         ///此时这个结点已经分到0.94以下，跳出
//                         is_allo = 1;
//                         break;
//                     }
//                     if (hand_back_index == clientInfo.everyTime_client_info[i].site_allo_list[k].size() - 1)
//                     {
//                     }
//                 }
//                 if (is_allo == 1)
//                 {
//                     /**
//                      * 该节点可以分配，那就这么做吧
//                      */
//                     //                    clientInfo.everyTime_client_info[i].copy(tmp_currentTime_client_info);
//                     //                    cout<<"可以执行，清空栈"<<endl;
//                     while (!redo_log.empty())
//                     {
//                         redo_log.pop();
//                     }
//                     /**
//                      * 该节点已经分配到0.94的范围了，这时候需要重新调整一下第k个边缘节点的0.95分位点
//                      */
//                 }
//                 else if (is_allo == 0)
//                 {
//                     /**
//                      * 不可以这么做，执行日志回访操作
//                      */
//                     //                     cout<<"不可以执行，进行回放"<<endl;
//                     while (!redo_log.empty())
//                     {

//                         clientInfo.everyTime_client_info[i].cost[redo_log.top().current_k] -= redo_log.top().bandwidth;
//                         clientInfo.everyTime_client_info[i].cost[redo_log.top().k] += redo_log.top().bandwidth;
//                         clientInfo.everyTime_client_info[i].allo_stream_client_toSite[redo_log.top().streamNum][redo_log.top().clientNum] = redo_log.top().k;
//                         clientInfo.everyTime_client_info[i].site_allo_list[k].push_back(clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k][clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].size() - 1]);
//                         clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].erase(std::begin(clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k]) + (clientInfo.everyTime_client_info[i].site_allo_list[redo_log.top().current_k].size() - 1));
//                         redo_log.pop();
//                     }
//                 }
//             }
//         }
//     }
// }

// void refine_solution(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
// {
//     float up_quantile = 0.95;
//     float down_quantile = 0.948;
//     int max_first_local_opt_iter = 500;
//     for (int _i = 0; _i < max_first_local_opt_iter; _i++)
//     {
//         local_optimization(clientInfo, siteInfo, qoSInfo, up_quantile, down_quantile);
//     }

//     // int iter_i = 130;
//     // while (iter_i--)
//     // {
//     //     out_local_optimization(clientInfo, siteInfo, qoSInfo, up, down);
//     //     // if (lunci > 117)
//     //     // kunkun_dream2_local_optimization(clientInfo, siteInfo, qoSInfo, 0.9501, down, dream_cost);
//     //     // local_optimization_pro(clientInfo, siteInfo, qoSInfo, up, down, dream_cost);

//     //     cout << "局部最小解到达,正在尝试突破,还剩下" << lunci << "次突破" << endl;
//     //     if (check_sum == sum_cost(clientInfo, siteInfo, qoSInfo))
//     //     {
//     //         break;
//     //     }
//     //     else
//     //         check_sum = sum_cost(clientInfo, siteInfo, qoSInfo);
//     // }
}
//////////////////////////////////////////////////////////////////////////////////////
// 坤坤代码结束：优化解相关函数
//////////////////////////////////////////////////////////////////////////////////////

void output_solution(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
{
    ofstream outFile;
    outFile.open(OUTPUT_FILE, ios::out); // 打开模式可省略

    endTime = clock(); //计时结束
    cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
    // check_error(clientInfo, siteInfo, qoSInfo);
    ///最后的输出文件
    for (int i = 0; i < clientInfo.everyTime_client_info.size(); i++)
    {
        for (int j = 0; j < clientInfo.client_number; j++)
        {
            outFile << clientInfo.client_Name[j] << ":";
            int fflag = 0;
            for (int s = 0; s < clientInfo.everyTime_client_info[i].streamNumber; s++)
            {
                int tmp_k = clientInfo.everyTime_client_info[i].allo_stream_client_toSite[s][j];
                if (tmp_k == -1)
                    continue;
                if (tmp_k > siteInfo.site_name.size())
                    cout << "你越界了" << endl;
                if (fflag == 0)
                {
                    outFile << "<" << siteInfo.site_name[tmp_k] << "," << clientInfo.everyTime_client_info[i].streamName[s] << ">";
                    fflag = 1;
                }
                else
                    outFile << ",<" << siteInfo.site_name[tmp_k] << "," << clientInfo.everyTime_client_info[i].streamName[s] << ">";
            }

            outFile << endl;
        }
    }

    outFile.close();
}

void insite_solution(Client_info &clientInfo, Site_Bandwidth_info &siteInfo, QoS_info &qoSInfo)
{
    int site_id = 54;

    for (int t = 0; t < clientInfo.clinet_timestamp_number; t++)
    {
    }
}

int main()
{
    startTime = clock(); //计时开始
    Client_info clientInfo;
    clientInfo.read_from_scv(DEMAND);
    Site_Bandwidth_info siteInfo;
    siteInfo.read_from_scv(SITE_BANDWIDTH);
    QoS_info qoSInfo;
    qoSInfo.read_QoS_constraint_from_scv(CONFIG);
    qoSInfo.read_QoS_from_scv(QOS, clientInfo.clientToIdx, siteInfo.siteToIdx);
    qoSInfo.read_client_to_site(clientInfo, siteInfo);


    init_solution(clientInfo, siteInfo, qoSInfo);
    init_site_to_site(clientInfo, siteInfo, qoSInfo);
    sum_cost(clientInfo, siteInfo, qoSInfo);
    refine_solution(clientInfo, siteInfo, qoSInfo);
//     insite_solution(clientInfo, siteInfo, qoSInfo);
    output_solution(clientInfo, siteInfo, qoSInfo);
}
